package parens;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author Seabook
 *
 */
public class BracketMatch {
	private static final String PAIR = "()";

	public static void main(String[] args) {
		BracketMatch bm = new BracketMatch();
		Set<String> initPair = new HashSet<String>();
		initPair.add(PAIR);
		Set<String> result = bm.recursionComposeBrackets(initPair, 4);
		//Set<String> result = bm.composeBrackets(4);
		System.out.println(result);
	}

	// n is pairs
	public Set<String> composeBrackets(int n) {
		Set<String> pairs = new HashSet<String>();
		pairs.add(PAIR);

		if (n == 1) {
			return pairs;
		} else {
			Set<String> temp = buildNewBrackets(pairs);
			for (int i = 3; i <= n; i++) {
				temp = buildNewBrackets(temp);
			}

			return temp;
		}
	}

	public Set<String> buildNewBrackets(Set<String> pairs) {
		Set<String> result = new HashSet<String>();

		for (String pair : pairs) {
			// System.out.println("Pair: " + pair);
			char[] pairCharArr = pair.toCharArray();
			for (int i = 0; i <= pairCharArr.length; i++) {
				StringBuilder sb = new StringBuilder(pair);
				sb.insert(i, PAIR);
				// System.out.println(sb.toString());
				result.add(sb.toString());
			}
		}

		return result;
	}

	public Set<String> recursionComposeBrackets(Set<String> pairs, int n) {
		if (n == 1) {
			//pairs.add(PAIR);
			return pairs;
		} else if (n == 2) {
			pairs = buildNewBrackets(pairs);
			return pairs;
		} else {
			pairs = recursionComposeBrackets(buildNewBrackets(pairs), --n);
			return pairs;
		}
	}
}
